package esercitazione4.BTree;

import java.util.ArrayList;

public class BTree<K extends Comparable<K>, V>  implements BTreeInterface<K,V>{
	// Dimensione massima di chiavi nel nodo (2*t+1)
	private static int MAX_DIM;
	// Dimensione minima di chiavi nel nodo (t)
	private static int MIN_DIM;
	// radice dell'albero
	private BNode<K,V> root;
	//altezza dell'albero
	private int heightTree;
	// numero di chiavi inserite nell'albero
	private int size;

	/**
	 * costruttore dell'albero, inizializza un nodo vuoto
	 * @param dimension_min dimensione minima delle chiavi
	 */
	public BTree(int dimension_min){
		MIN_DIM = dimension_min - 1;
		MAX_DIM = dimension_min * 2 - 1;
		root = new BNode<K,V>();
	}

	/**
	 * restituisce il numero di livelli presenti nell'albero
	 */
	public int height(){
		// poichè è l'altezza dell'albero senza considerare il livello root
		return heightTree + 1;
	}

	/**
	 * restituisce il numero di entry presenti nell'albero
	 */
	public int size(){
		return size;
	}

	/**
	 * Ritorna il valore di un nodo, data la chiave
	 */
	public V get(K key) throws NoKeyFoundException {
		Element<K,V> result = search(root, key, heightTree);
		if(result != null)
			return result.getValue();
		else
			throw new NoKeyFoundException();
	}

	// 
	/**
	 * ricerca una chiave all'interno dell'albero e se presente restituisce l'entry ad essa relativa
	 * @param node Nodo da cui partire
	 * @param key Chiave da ricercare
	 * @param height	Altezza dell'albero
	 */
	private Element<K,V> search(BNodeInterface<K,V> node, K key, int height) {
		// se è un nodo foglia
		if(height == 0) {
			for (int j = 0; j < node.getNumberOfChild(); j++) {
				if (node.getChild().get(j).getKey().compareTo(key) == 0 )
					return node.getChild().get(j);
			}
		}
		// se non è un nodo foglia
		else{
			for (int j = 0; j < node.getNumberOfChild(); j++) {
				// se è minore della prima chiave
				if(j == 0 && key.compareTo(node.getChild().get(j).getKey()) < 0)
					return search(node.getPrec(), key, height-1);
				// se è minore di una qualsiasi altra chiave del nodo
				else if (j + 1 == node.getNumberOfChild() || key.compareTo(node.getChild().get(j+1).getKey()) < 0)
					return search(node.getChild().get(j).getNext(), key, height-1);
			}
		}
		return null;
	}

	
	/** Aggiunge una entry all'interno dell'albero
	 * @param key Chiave della entry da inserire
	 * @param value Valore della entry da inserire
	 * @throws KeyDuplicateException
	 */
	public void add(K key, V value) throws KeyDuplicateException {
		BNodeInterface<K, V> node = insert(root, key, value, heightTree);

		// se il nodo (node) è vuoto => l'inserimento non ha generato riporti nell'operazione di inserimento
		// se il nodo (node) non è vuoto => bisogna effettuare operare sulla root per legare il riporto (node) all'albero (root)
		// OPERAZIONE: prendo (0, root) e (0, node) e li inserisco in una nuova (newRoot)
		if (node != null){
			BNode<K,V> newRoot = new BNode<K,V>();
			// node-part
			newRoot.getChild().add(node.getChild().get(0));
			node.getChild().remove(0);
			if(newRoot.getChild().get(0).getNext() != null)
				node.setPrec((BNode<K,V>) newRoot.getChild().get(0).getNext());
			newRoot.getChild().get(0).setNext(node);
			// root-part
			newRoot.setPrec(root);

			//assegno la nuova root e aggiungo un livello all'albero
			root = (BNode<K,V>) newRoot;
			heightTree++;
		}
	}

	/**
	 * inserisce in un nodo e verifica eventualmente se il nodo si è riempito
	 * @param node Nodo in cui inserire la entry
	 * @param key	Chiave della entry
	 * @param value	Valore della entry
	 * @param height	altezza dell'albero
	 * @throws KeyDuplicateException
	 */
	private BNodeInterface<K,V> insert(BNodeInterface<K,V> node, K key, V value, int height) throws KeyDuplicateException {
		int j;
		Element<K,V> element = new Element<K,V>(key, value, null);
		BNodeInterface<K,V> splitResult = null;

		// CASO 1 - nodo foglia => ho indice e elemento da inserire (j, element)
		if (height == 0) {
			for (j = 0; j < node.getNumberOfChild(); j++) {
				if(key.compareTo(node.getChild().get(j).getKey()) == 0)
					throw new KeyDuplicateException();
				else if (key.compareTo(node.getChild().get(j).getKey()) < 0)
					break;
			}

			// aggiungo il nuovo elemento
			node.getChild().add(j, element);
			size++;
		}

		// CASO 2 - nodo non foglia => richiamo insert su figlio giusto (in base a indice j)
		//			SE mio figlio ha inserito element, ma ha dovuto fare split.
		//			il nodo ottenuto da split (splitResult) devo collegarlo al padre
		//			ho già l'elemento da aggiungere nel nodo padre (element)
		//			l'indice in cui inserire il nodo l'ho ottenuto dal for all'interno dell'else (j)
		else {
			for (j = 0; j < node.getNumberOfChild(); j++) {
				if(key.compareTo(node.getChild().get(j).getKey()) == 0)
					throw new KeyDuplicateException();
				// se è minore della prima chiave
				else if(j == 0 && key.compareTo(node.getChild().get(j).getKey()) < 0){
					// chiamo la insert su nodo figlio (prec) precedente a qualunque mia chiave
					splitResult = insert(node.getPrec(), key, value, height-1);

					// un mio figlio ha restituito un nodo da inserire nel BTree e che io padre devo collegare
					// allora prendo il primo elemento e lo inserisco nel mio nodo padre
					// e lo elimino dal nodo figlio
					// poi devo collegarlo all'elemento appena inserito
					if(splitResult != null)
						solveSplit(node, splitResult, j);
					break;
				}
				else if (j + 1 == node.getNumberOfChild() || key.compareTo(node.getChild().get(j+1).getKey()) < 0){
					// chiamo la insert su un nodo figlio
					splitResult = insert(node.getChild().get(j).getNext(), key, value, height-1);			

					// un mio figlio ha restituito un nodo da inserire nel BTree e che io padre devo collegare
					// allora prendo il primo elemento e lo inserisco nel mio nodo padre
					// e lo elimino dal nodo figlio
					// poi devo collegarlo all'elemento appena inserito
					if(splitResult != null)
						solveSplit(node, splitResult, j+1);
					break;
				}
			}
		}

		// se ho riempito il nodo, allora devo dividerlo
		if (node.getNumberOfChild() > MAX_DIM)
			return split(node);
		else
			return null;
	}


	/**
	 * divide un nodo, e ciò che ne rimane lo ritorna come output
	 * @param node Nodo da dividere
	 */
	private BNodeInterface<K,V> split(BNodeInterface<K,V> node) {
		// 1- crea un nuovo nodo con la seconda metà elementi del nodo da splittare
		BNodeInterface<K,V> newNode = new BNode<K,V>();
		// gli indici sono (+ 1) poichè in questo caso il nodo ha un elemento più del normale
		for (int j = MIN_DIM + 1; j < MAX_DIM + 1; j++)
			newNode.getChild().add(node.getChild().get(j));

		// 2- rimuove gli elementi nel nodo (node) inseriti nel nuovo nodo (newNode)
		for (int j = MAX_DIM; j > MIN_DIM; j--)
			node.getChild().remove(j);

		// 3- adesso il nodo (node) è collegato, ma privato di elementi che adesso sono nel nuovo nodo (newNode)
		// il nuovo nodo (newNode) deve tornare al nodo padre per essere sistemato
		return newNode;
	}

	/**
	 * metodo per risolvere una situazione di split dopo una insert
	 */
	private void solveSplit(BNodeInterface<K,V> node, BNodeInterface<K,V> splitResult, int index){
		node.getChild().add(index,splitResult.getChild().get(0));
		splitResult.getChild().remove(0);
		if(node.getChild().get(index).getNext() != null)
			splitResult.setPrec((BNode<K,V>) node.getChild().get(index).getNext());
		node.getChild().get(index).setNext(splitResult);
	}

	/**
	 * Cancella una entry
	 * @param key Chiave della entry da cancellare
	 * @throws NoKeyFoundException
	 * @throws TreeEmptyException
	 */
	@Override
	public boolean delete(K key) throws NoKeyFoundException, TreeEmptyException {
		if(root != null){
			remove(root, key, heightTree);
			if(root.getNumberOfChild() == 0){
				root = root.getPrec();
				if(heightTree > 0)
					heightTree--;
			}

			// se l'albero è stato completamente cancellato, lo re-inizializza
			if(size == 0)
				root = new BNode<K,V>();

			return true;
		}
		else
			throw new TreeEmptyException();
	}

	/**
	 * se la chiave è presente rimuove l'entry relativa e la restituisce
	 * @param node Nodo in cui viene controllata la presenza della chiave
	 * @param key	Chiave della entry da cancellare
	 * @param height Altezza del sottoalbero
	 * @throws NoKeyFoundException
	 */
	private void remove(BNodeInterface<K,V> node, K key, int height) throws NoKeyFoundException{
		// CASO 1 - nodo foglia
		// se c'è lo elimina
		if (height == 0) {
			Element<K,V> deleted = null;
			for (int j = 0; j < node.getNumberOfChild(); j++) {
				if (key.compareTo(node.getChild().get(j).getKey()) == 0){
					deleted = node.getChild().remove(j);
					size--;
				}
			}
			if(deleted == null)
				throw new NoKeyFoundException();
		}
		// CASO 2 - nodo non foglia
		// a) se è uguale => cancello il nodo sostituendolo con il predecessore
		// b) altrimenti si invoca ricorsivamente il metodo sul figlio che potrebbe contenere quella chiave
		else{
			for (int j = 0; j < node.getNumberOfChild(); j++) {
				//Itero nel prev del nodo se key è minore di tutte le chiavi del nodo
				if(j == 0 && key.compareTo(node.getChild().get(j).getKey()) < 0){
					// verifico che il nodo non ha numero di chiavi minime e eventualmente ri-bilancio l'albero
					if(node.getPrec().getNumberOfChild() <= MIN_DIM)
						adjustTree(node, -1);
					// rimuovo la entry e infine verifico che l'albero sia bilanciato
					remove(node.getPrec(), key, height - 1);
					break;
				}
				// Trovo elemento nel nodo non foglia
				else if (key.compareTo(node.getChild().get(j).getKey()) == 0){
					boolean isMerged = false;
					// verifico che il nodo non ha numero di chiavi minime e eventualmente ri-bilancio l'albero
					if(j == 0){
						if(node.getPrec().getNumberOfChild() <= MIN_DIM)
							isMerged = adjustTree(node, -1);
					}
					else{
						if(node.getChild().get(j - 1).getNext().getNumberOfChild() <= MIN_DIM)
							isMerged = adjustTree(node, j - 1);
					}

					// a questo punto l'adjustTree può aver portato l'albero nelle seguenti condizioni:
					// 1) Merge => significa che key è adesso nel figlio precedente (j-1.next)
					//			   allora j = j-1
					//				1a) se adesso j = -1, allora cerco nel prec
					//				1b) se adesso j >= 0, allora cerco nel j.next
					// 2) RotationSx => significa che key è nel figlio precedente (j-1.next)
					//					allora j = j - 1
					//					1a) se adesso j = -1, allora cerco nel prec
					//				    1b) se adesso j >= 0, allora cerco nel j.next
					// 3) Rotation Dx => Poichè l'adjust controlla la condizione del figlio precedente, in quel caso la key rimane in k.
					// 4) No-op => significa che key è ancora in posizione j

					// (caso 1) se k è stato spostato, poichè frutto di un merge/rotationSx (dovuto a adjustTree)
					if(isMerged)
						j = j - 1;

					// (caso 3 e 4) se k è ancora in node(j)
					if(j >= 0 && key.compareTo(node.getChild().get(j).getKey()) == 0){
						V value = node.getChild().get(j).getValue();
						node.getChild().add(j, swapWithNeighbor(key, value, node, j, height));
						node.getChild().get(j).setNext(node.getChild().get(j+1).getNext());
						node.getChild().remove(j+1);
						if(j == 0)
							remove(node.getPrec(), key, height - 1);
						else
							remove(node.getChild().get(j - 1).getNext(), key, height - 1);
					}
					// (caso 1) se k non è in node, ma nel prec
					else if(j == -1){
						remove(node.getPrec(), key, height - 1);
					}
					// (caso 2) se k non è in node, ma nel j-1.next (ma j == 0)
					else if(j == 0 && !isMerged){
						remove(node.getPrec(), key, height - 1);
					}
					// (caso 1 e 2) se k non è in node, ma nel next del precedente
					else{
						// (caso 2) devo andare nel precedente, e quindi nel j-1.next
						if(!isMerged)
							remove(node.getChild().get(j - 1).getNext(), key, height - 1);
						// (caso 1) ho già aggiornato j, quindi devo andare nel j.next
						else
							remove(node.getChild().get(j).getNext(), key, height - 1);
					}
					break;
				}	
				// Itero nel giusto nodo.next
				else if(j + 1 == node.getNumberOfChild() || key.compareTo(node.getChild().get(j+1).getKey()) < 0){
					boolean isMerged = false;
					// verifico che il nodo non ha numero di chiavi minime e eventualmente ri-bilancio l'albero
					if(node.getChild().get(j).getNext().getNumberOfChild() <= MIN_DIM)
						isMerged = adjustTree(node, j);

					// se k è stato spostato, poichè frutto di un merge/rotazione a dx (dovuto a adjustTree) => TRUE
					if(isMerged)
						j = j - 1;

					if(isMerged && j == -1)
						remove(node.getPrec(), key, height - 1);
					else if(j == 0 && key.compareTo(node.getChild().get(j).getKey()) < 0)
						remove(node.getPrec(), key, height - 1);
					else
						remove(node.getChild().get(j).getNext(), key, height - 1);
					break;
				}
			}
		}
	}

	// metodo per verificare che il nodo (next) dell'albero non abbia numero di chiavi minimo
	// metodo per bilanciare l'albero con un nodo con numero di chiavi minimo
	// (index) indice dell'entry all'interno del nodo che aveva come next il nodo da riparare
	// (node) è il nodo corrente, padre di quello da riparare
	// METODO 1) pseudo-rotazione
	// METODO 2) merge
	// ritorna BOOLEAN = TRUE se è stata fatta una qualsiasi operazione
	
	/**
	 * metodo per verificare che il nodo (next) dell'albero non abbia numero di chiavi minimo
	 * metodo per bilanciare l'albero con un nodo con numero di chiavi minimo
	 * METODO 1) pseudo-rotazione
	 * METODO 2) merge
	 * @param node	 è il nodo corrente, padre di quello da riparare
	 * @param index indice dell'entry all'interno del nodo che aveva come next il nodo da riparare
	 * @return true se è stata fatta una qualsiasi operazione
	 */
	private boolean adjustTree(BNodeInterface<K,V> node, int index){
		ArrayList<BNodeInterface<K,V>> sibling = getNodeSibling(node, index);

		// METODO 1
		for(int i = 0; i < sibling.size(); i++){
			if(sibling.get(i) != null){
				if(sibling.get(i).getNumberOfChild() > MIN_DIM){
					if(i == 0)
						pseudoRotateTree(node, index, true);
					else
						pseudoRotateTree(node, index, false);
					return false;
				}
			}
		}

		// METODO 2
		for(int i = 0; i < sibling.size(); i++){
			if(sibling.get(i) != null){
				if(sibling.get(i).getNumberOfChild() == MIN_DIM){
					BNodeInterface<K,V> precOverflow = null;
					int middleIndex;
					if(i == 0){
						middleIndex = sibling.get(i).getNumberOfChild();
						precOverflow = merge(sibling.get(i), node.getChild().get(index).getNext());
						sibling.get(i).getChild().add(middleIndex, node.getChild().remove(index));
						sibling.get(i).getChild().get(middleIndex).setNext(precOverflow);
					}
					else{
						if(index == -1){
							middleIndex = node.getPrec().getNumberOfChild();
							precOverflow = merge(node.getPrec(), sibling.get(i));
							node.getPrec().getChild().add(middleIndex, node.getChild().remove(index + 1));
							node.getPrec().getChild().get(middleIndex).setNext(precOverflow);
						}
						else{
							middleIndex = node.getChild().get(index).getNext().getNumberOfChild();
							precOverflow = merge(node.getChild().get(index).getNext(), sibling.get(i));
							node.getChild().get(index).getNext().getChild().add(middleIndex, node.getChild().remove(index + 1));
							node.getChild().get(index).getNext().getChild().get(middleIndex).setNext(precOverflow);
						}
					}
					return true;
				}
			}
		}
		return false;
	}

	
	/**
	 * metodo per fondere il secondo nodo col primo (copiando il primo nodo nel secondo)
	 * @param node1 
	 * @param node2
	 * @return l'indice che servirà al padre per inserire l'entry che è in mezzo ai due nodi figli da fondere
	 */
	private BNodeInterface<K,V> merge(BNodeInterface<K,V> node1, BNodeInterface<K,V> node2){
		for(int index = 0; index < node2.getNumberOfChild(); index++)
			node1.getChild().add(node2.getChild().get(index));

		if(node2.getPrec() != null)
			return node2.getPrec();
		else
			return null;
	}

	
	/**
	 * metodo per pseudoruotare l'albero con un sibling
	 * @param node		E' il nodo padre
	 * @param index		E' l'indice dell'entry del nodo padre il cui (next) deve essere riparato
	 * @param isRightRotation 
	 */
	private void pseudoRotateTree(BNodeInterface<K,V> node, int index, boolean isRightRotation){
		BNodeInterface<K,V> rotationOverflow = null;
		if(isRightRotation){
			Element<K,V> max_child;
			// in questo caso non posos avere (index = -1) perchè non posso fare una rotazione a destra
			// (poichè non esiste mai sibling sinistro di Prec)
			// quindi index - 1 esiste sempre
			if(index == 0)
				max_child = getMax(node.getPrec(), 0);
			else
				max_child = getMax(node.getChild().get(index - 1).getNext(), 0);
			node.getChild().add(index, max_child);
			rotationOverflow = node.getChild().get(index).getNext();
			node.getChild().get(index).setNext(node.getChild().get(index + 1).getNext());
			Element<K,V> tmp = node.getChild().remove(index + 1);
			tmp.setNext(node.getChild().get(index).getNext().getPrec());
			node.getChild().get(index).getNext().setPrec((BNode<K, V>) rotationOverflow);
			node.getChild().get(index).getNext().getChild().add(0, tmp);
		}
		else{
			// in questo caso non posso avere (index = numChild) perchè non posso fare rotazione a sinistra
			// (poichè non esiste mai sibling destro dell'ultimo next)
			// quindi index + 1 esiste sempre
			Element<K,V> min_child = getMin(node.getChild().get(index + 1).getNext(), 0);
			node.getChild().add(index + 1, min_child);
			rotationOverflow = node.getChild().get(index + 2).getNext().getPrec();
			node.getChild().get(index + 2).getNext().setPrec((BNode<K, V>) node.getChild().get(index + 1).getNext());
			node.getChild().get(index + 1).setNext(node.getChild().get(index + 2).getNext());
			Element<K,V> tmp = node.getChild().remove(index + 2);
			tmp.setNext((BNode<K, V>) rotationOverflow);

			// se index == -1 significa che devo andare nel prec
			// altrimenti devo andare in index
			if(index == -1)
				node.getPrec().getChild().add(tmp);
			else
				node.getChild().get(index).getNext().getChild().add(tmp);
		}
	}

	/**
	 * metodo che dato il Padre e la Chiave di uno dei figli, restituisce tutti i nodi fratelli del nodo contenente la Chiave.
	 * @param node
	 * @param index
	 */
	private ArrayList<BNodeInterface<K,V>> getNodeSibling(BNodeInterface<K,V> node, int index){
		ArrayList<BNodeInterface<K,V>> sibling = new ArrayList<BNodeInterface<K,V>>(2);

		// se il nodo da riparare è il prev
		if(index == -1){
			sibling.add(0, null);
			sibling.add(1, node.getChild().get(0).getNext());
		}
		// se il nodo da riparare è il next della prima entry
		else if(index == 0){
			sibling.add(0, node.getPrec());
			if((index + 1) < (node.getNumberOfChild() - 1) && node.getChild().get(index + 1) != null)
				sibling.add(1, node.getChild().get(index + 1).getNext());
			else
				sibling.add(1, null);
		}
		// se il nodo da riparare è il next dell'ultima entry
		else if(index == node.getNumberOfChild() - 1){
			sibling.add(0, node.getChild().get(index - 1).getNext());
			sibling.add(1, null);
		}
		// se il nodo da riparare è il next di una entry generica
		else{
			if((index - 1) >= 0 && node.getChild().get(index - 1) != null)
				sibling.add(0, node.getChild().get(index - 1).getNext());
			else
				sibling.add(0, null);
			if((index + 1) <= (node.getNumberOfChild() - 1) && node.getChild().get(index + 1) != null)
				sibling.add(1, node.getChild().get(index + 1).getNext());
			else
				sibling.add(1, null);
		}

		return sibling;
	}

	
	/**
	 * metodo per individuare il predecessore di una chiave (key) del nodo (node) nei suoi nodi figli
	 * (index) è la posizione dell'entry, con chiave (key), all'interno del nodo (node)
	 */
	private Element<K,V> swapWithNeighbor(K key, V value, BNodeInterface<K,V> node, int index, int height){
		if(index == 0){
			if(node.getPrec() != null)
				return swapWithMaxNeighbor(node.getPrec(), key, value, height - 1);
			else
				return swapWithMinNeighbor(node.getChild().get(index).getNext(), key, value, height - 1);
		}
		else{
			if(node.getChild().get(index - 1).getNext() != null)
				return swapWithMaxNeighbor(node.getChild().get(index - 1).getNext(), key, value, height - 1);
			else
				return swapWithMinNeighbor(node.getChild().get(index).getNext(), key, value, height - 1);
		}
	}

	/**
	 * scambia l'entry (key, value) con l'entry immediatamente maggiore presente nell'albero
	 */
	private Element<K,V> swapWithMaxNeighbor(BNodeInterface<K,V> node, K key, V value, int height){
		if(height == 0){
			Element<K,V> result = node.getChild().remove(node.getNumberOfChild() - 1);
			node.getChild().add(new Element<K,V>(key, value, null));
			return result;
		}
		else
			return swapWithMaxNeighbor(node.getChild().get(node.getNumberOfChild() - 1).getNext(), key, value, height - 1);
	}


	/**
	 * scambia l'entry (key, value) con l'entry immediatamente minore presente nell'albero
	 */
	private Element<K,V> swapWithMinNeighbor(BNodeInterface<K,V> node, K key, V value, int height){
		if(height == 0){
			Element<K,V> result = node.getChild().remove(0);
			node.getChild().add(new Element<K,V>(key, value, null));
			return result;
		}
		else
			return swapWithMinNeighbor(node.getPrec(), key, value, height - 1);
	}

	/**
	 * metodo per rimuovere il massimo valore chiave all'interno di un sottoalbero
	 */
	private Element<K,V> getMax(BNodeInterface<K,V> node, int height){
		if(height == 0)
			return node.getChild().remove(node.getNumberOfChild() - 1);
		else
			return getMax(node.getChild().get(node.getNumberOfChild() - 1).getNext(), height - 1);
	}

	/**
	 * metodo per rimuovere il minimo valore chiave all'interno di un sottoalbero
	 */	private Element<K,V> getMin(BNodeInterface<K,V> node, int height){
		if(height == 0)
			return node.getChild().remove(0);
		else
			return getMax(node.getPrec(), height - 1);
	}

	 /**
	  * Stampa l'albero
	  */
	@Override
	public String toString() {
		return toString(root, heightTree, "") + "\n";
	}

	/**
	 * Stampa un nodo
	 */
	private String toString(BNodeInterface<K,V> node, int height, String indent) {
		String s = "";
		if(node != null){
			ArrayList<Element<K,V>> children = node.getChild();

			if(node.getPrec() != null)
				s += toString(node.getPrec(), height-1, indent + "     ");

			if (height == 0) {
				for (int j = 0; j < children.size(); j++) {
					s += indent + children.get(j).getKey() + " - " + children.get(j).getValue() + "\n";
				}
			}
			else {
				for (int j = 0; j < children.size(); j++) {
					s += indent + children.get(j).getKey() + " - " + children.get(j).getValue() + "\n";
					s += toString(children.get(j).getNext(), height-1, indent + "     ");
				}
			}

			return s;
		}
		else
			return indent + "NODO VUOTO\n";

	}
}